package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;

/*
n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高。
每一个物体都可以只取走一部分，价值和重量按比例计算。

注意：每个物体可以只拿一部分，因此一定可以让总重量恰好为C！

in
6
1 2 3 4 5 6
5 5 5 5 4 1
20

out
20
 */
public class e背包问题by贪心plus部分切割 {
	public static void main(String[] args) {
		e背包问题by贪心plus部分切割 test = new e背包问题by贪心plus部分切割();
		test.useGreedyAlgorithmKnapsack2();
	}
	
	/**
	 * 前置方法
	 */
	public void useGreedyAlgorithmKnapsack2() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] value = new int[N];
		int[] weight = new int[N];
		for (int i = 0; i < N; i++) {
			value[i] = scanner.nextInt();
		}
		for (int i = 0; i < N; i++) {
			weight[i] = scanner.nextInt();
		}
		int maxWeight = scanner.nextInt();
		double res = GreedyAlgorithmKnapsack2(value, weight, N, maxWeight);
		System.out.println(res);
	}
	
	/**
	 * 贪心
	 * 选单价最高的
	 * @param value
	 * @param weight
	 * @param N
	 * @param currentWeight
	 * @return
	 */
	public double GreedyAlgorithmKnapsack2(int[] value, int[] weight, int N, int currentWeight) {
		double res = 0;
		Obj[] objs = new Obj[N];
		for (int i = 0; i < N; i++) {
			objs[i] = new Obj(weight[i], value[i]);//打包思想
		}
		Arrays.sort(objs);
		for (int i = N - 1; i >= 0; i--) {
			if (objs[i].weight < currentWeight) {//整个带走
				res += objs[i].value;
				currentWeight -= objs[i].weight;
			} else {//切割
				res += currentWeight * objs[i].getUnitPrice();
				return res;
			}
		}
		return res;
	}
	
	private static class Obj implements Comparable<Obj> {
		int weight;
		int value;
		public Obj(int wight, int value) {
			this.weight = wight;
			this.value = value;
		}
		public double getUnitPrice() {
			return (double) value / weight;
		}
		@Override
		/**
		this是新元素，other是老元素
		this.string.compareTo(other.string)会返回一个int A
		Suff类的compareTo会返回一个int,实际上就是把A返回
		在使用了自然排序的集合中添加Suff类对象
		这些对象的顺序是根据A决定的
		A = 0，在有些集合中，新元素(this)就不会加入；Array.sort不会导致“不加入”
		A > 0，this在other后面加入
		A < 0，this在other前面加入
		 */
		public int compareTo(Obj o) {
			int x = (int) (this.getUnitPrice() - o.getUnitPrice());
			if (x == 0) {
				return this.weight - o.weight;//单价一样，谁轻谁在前面
			}
			return x;
		}
	}
}
